#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct TreeNode
{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

void PostOrder(struct TreeNode* root, int* a, int* aSize)
{
    if (root == NULL)
    {
        return;
    }
    PostOrder(root->left, a, aSize);
    PostOrder(root->right, a, aSize);
    a[(*aSize)++] = root->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int* a = malloc(sizeof(int) * 3000);
    *returnSize = 0;
    PostOrder(root, a, returnSize);
    return a;
}

void InOrder(struct TreeNode* root, int* a, int* aSize)

{

    if (root == NULL)

    {

        return;

    }

    InOrder(root->left, a, aSize);

    a[(*aSize)++] = root->val;

    InOrder(root->right, a, aSize);

}



int* inorderTraversal(struct TreeNode* root, int* returnSize) {

    int* a = malloc(sizeof(int) * 1000);

    *returnSize = 0;

    InOrder(root, a, returnSize);



    return a;

}

bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2) {
    if (root1 == NULL && root2 == NULL)
        return true;
    if (root1 == NULL || root2 == NULL)
        return false;
    if (root1->val != root2->val)
        return false;

    return _isSymmetric(root1->left, root2->right)
        && _isSymmetric(root1->right, root2->left);
}

bool isSymmetric(struct TreeNode* root) {
    return _isSymmetric(root->left, root->right);
}

int height(struct TreeNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    else
    {
        return fmax(height(root->left), height(root->right)) + 1;
    }
}

bool isBalanced(struct TreeNode* root) {
    if (root == NULL)
    {
        return true;
    }
    else {
        return fabs(height(root->left) - height(root->right)) <= 1
            && isBalanced(root->left)
            && isBalanced(root->right);
    }
}